package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 17:40 2020/8/8
 * @Description  二叉树的层次遍历
 *
 * 二叉树：[3,9,20,null,null,15,7],
        3
       / \
      9  20
        /  \
       15   7
     [
      [3],
      [9,20],
      [15,7]
     ]

     */

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class LevelOrder {

    /**
     * 层次遍历需要使用到队列
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        //此处返回不能是null，要是一个数组
        if (root == null) return new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        List<List<Integer>> ans = new ArrayList<>();
        while (deque.size() > 0) {
            List<Integer> list = new ArrayList<>();
            // 此处一定不要写deque.size()因为它会动态变化，影响for循环，必须先拿出来
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.remove();
                list.add(node.val);
                if (node.left != null) deque.add(node.left);
                if (node.right != null) deque.add(node.right);
            }
            ans.add(list);
        }
        return ans;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
